Ngày 8 tháng 3 năm 1949, Hiệp ước Élysée công nhận chính phủ Quốc gia Việt Nam nằm trong Liên hiệp Pháp, cùng với lực lượng quân đội riêng của quốc gia này. Theo Nghị định Quốc phòng ngày 13 tháng 4 năm 1949, một lực lượng quân đội của Quốc gia Việt Nam được thành lập, lấy tên là Vệ binh Quốc gia[1] sẽ cùng phối hợp và nhận sự chỉ huy của quân đội Pháp để đánh lại Việt Minh.

Ngày 11 tháng 5 năm 1950, Thủ tướng Trần Văn Hữu tuyên bố chính thức thành lập Vệ binh Quốc gia Việt Nam với quân số lúc đó là 60.000 người [2].

Ngày 8 tháng 12 năm 1950, Quốc gia Việt Nam và Pháp ký Hiệp định quân sự thành lập Quân đội Quốc gia Việt Nam bằng cách đặt một số đơn vị quân đội Pháp tại Việt Nam dưới quyền chỉ huy của Quốc gia Việt Nam. Cần lưu ý rằng trước đó, danh xưng Quân đội Quốc gia Việt Nam đã được quân đội của nước Việt Nam Dân chủ Cộng hòa sử dụng từ năm 1946.

Dự kiến quân đội này sẽ bao gồm 120.000 quân và 4.000 sĩ quan, tất cả sĩ quan đều phải là người Việt. Tuy nhiên, điều này không được thực hiện cho đến cuối năm 1951 khi Bộ Tổng tham mưu Quân đội Quốc gia Việt Nam được thành lập và dường như không có việc bổ nhiệm cho những đơn vị cụ thể cho đến cuối năm 1953.[3] Quốc trưởng Bảo Đại là tổng chỉ huy của Quân đội Quốc gia Việt Nam từ năm 1950 đến 1955.

Về việc thành lập Quân đội Quốc gia Việt Nam, tướng Jean de Lattre de Tassigny nhận xét người Việt có khả năng trở thành những chiến binh xuất sắc. Chỉ cần vài tuần huấn luyện là có thể tạo ra những đơn vị có khả năng tác chiến. Với số thanh niên đông đảo tại Việt Nam, nếu Quốc gia Việt Nam không tuyển mộ thì Việt Minh sẽ thu hút nguồn nhân lực đó. Vấn đề của Quân đội Quốc gia Việt Nam là thiếu chỉ huy người Việt. Để giải quyết vấn đề này cần sự trợ giúp của Mỹ. Nếu đặt dưới sự chỉ huy của sĩ quan Pháp thì đơn vị đó sẽ bị suy yếu.[3]

Trong nỗ lực thành lập Quân đội Quốc gia Việt Nam, vấn đề cơ bản là đào tạo sĩ quan và hạ sĩ quan. Quốc gia Việt Nam thừa nhận tình trạng thiếu những người được huấn luyện quân sự nhưng tuyên bố vì lý do chính trị, việc sử dụng sĩ quan Pháp là trở ngại. Pháp có trách nhiệm hỗ trợ Việt Nam trong công tác huấn luyện sĩ quan. Trong khi đó, Pháp lại không chấp nhận trang bị vũ khí cho những đơn vị Quân đội Quốc gia Việt Nam mới thành lập trừ khi Việt Nam chấp nhận một tỷ lệ nhất định sĩ quan Pháp trong Quân đội Quốc gia Việt Nam trong thời gian sĩ quan Việt Nam đang được đào tạo tại những cơ sở huấn luyện mới thành lập.[3]

Ngày 12 Tháng Tư, 1952 theo Nghị định 147/QĐ/NĐ thì chính phủ Quốc gia Việt Nam chính thức thành lập Bộ Tổng tham mưu cho Quân đội Quốc gia Việt Nam.[4] Quân đội Quốc gia Việt Nam có tổng tư lệnh là Quốc trưởng Bảo Đại và được đặt dưới quyền quản trị của Bộ Tổng Tham mưu. Tổng Tham mưu trưởng Quân đội Quốc gia Việt Nam đầu tiên là một sĩ quan người Việt quốc tịch Pháp, nguyên Đại tá Chánh Võ phòng của Quốc trưởng, tân Thiếu tướng Nguyễn Văn Hinh. Trụ sở Bộ Tổng Tham mưu đặt tại số 1 đường Galiéni, tức thành Ô Ma (Camp Aux Mares), Sài Gòn [5].

Trước khi quân đội của chính thể Quốc gia Việt Nam được thành lập thì tên gọi "Quân đội Quốc gia Việt Nam" đã được sử dụng với tư cách danh xưng chính thức của quân đội Việt Nam Dân chủ Cộng hòa từ năm 1946 (Theo Sắc lệnh 71/SL của Chủ tịch nước Việt Nam Dân chủ Cộng hòa ngày 22 tháng 5 năm 1946).